สิ่งที่เราจะสร้างขึ้น 🎯
- โครงสร้างข้อมูล: โครงสร้างข้อมูลที่เรียกว่า คิวความสำคัญ (PQ)។
- มันเป็นประเภทข้อมูลเชิงนามธรรม เช่นเดียวกับลิสต์หรือคิว แต่มีจุดพิเศษบางอย่าง
- ทุกรายการจะมี "ระดับความสำคัญ" (คีย์) ของตัวเอง
- เมื่อคุณใช้คำสั่ง "pop" คุณจะได้รับรายการที่มีเสมอรายการที่มีความสำคัญสูงสุด
- การทำงานที่จำเป็น:
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- การนำไปใช้งาน:เราจะใช้โครงสร้าง ฮีปแบบไบนารีสูงสุด។
- ทำไมต้องใช้ฮีป? มันมีประสิทธิภาพมาก! ฮีปช่วยให้เราได้ผลลัพธ์ดังนี้:
push: O(log N)pop: O(log N)peek: O(1)
ฮีปแบบสูงสุดคืออะไร?
ต้นไม้ไบนารีที่มีกฎสองข้อง่ายๆ:
1. คุณสมบัติรูปร่าง
เป็น ต้นไม้ไบนารีที่สมบูรณ์ทุกระดับเต็มหมด ยกเว้นระดับสุดท้าย ซึ่งอาจไม่เต็ม และจะถูกเติมจากซ้ายไปขวา ไม่มีช่องว่างใดๆ เลยไม่มีช่องว่าง។
คลิกใบหนึ่งเพื่อลบ
2. คุณสมบัติฮีปแบบสูงสุด
คีย์ของโหนดพ่อแม่ต้องเป็น มากกว่าหรือเท่ากับคีย์ของลูกหลาน ซึ่งทำให้มั่นใจได้ว่ารายการที่มีค่าสูงสุดจะอยู่ที่จุดรากเสมอค่ามากที่สุด รายการจะอยู่ที่จุดรากเสมอ
การเก็บข้อมูลต้นไม้ 💾
เนื่องจากต้นไม้นี้เป็น สมบูรณ์ เราสามารถเก็บข้อมูลไว้ในอาร์เรย์ธรรมดาได้อย่างสมบูรณ์
คณิตศาสตร์ดัชนี (เริ่มต้นที่ 0)
สำหรับโหนดที่อยู่ที่ดัชนี i:
- พ่อแม่
(i - 1) // 2 - ลูกซ้าย
2 * i + 1 - ลูกขวา
2 * i + 2
คำแนะนำ:จดจำสูตรเหล่านี้ให้ขึ้นใจ! มันคือกุญแจสำคัญในการนำทางต้นไม้ที่ซ่อนอยู่ภายในอาร์เรย์ของคุณ